import graph.graph as gt
import math

def adjacentlist(V, E):     #构建领接表
    Ea = []
    for w in V:
        e0 = [w]
        e1 = []
        for (u, v) in E:
            if u == w and (v not in e1):
                e1 = e1 + [v]
            if v == w and (u not in e1):
                e1 = e1 + [u]
        e0 = e0 + [sorted(e1)]
        Ea = Ea + [e0]
    return sorted(Ea)

def tourpath0(V, E, path, m):   #构建哈密顿第一步
    while (len(path) < m):
        w = path[-1]
        i = V.index(w)
        E1 = E[i]
        E2 = E1[1]
        for u in E2:
            if (u not in path):
                path.append(u)
                break
        if path[-1] == w:
            break
    return path

def tourpath1(V, E, path, m):   #构建哈密顿第二步
    v = path.pop()
    while (len(path) != 0):
        u = path[-1]
        i = V.index(u)
        E1 = E[i]
        E2 = E1[1]
        k = E2.index(v)
        while (k < (len(E2) - 1)):
            k = k + 1
            v = E2[k]
            if (v not in path):
                path.append(v)
                break
        if (u != path[-1]):
            break
        v = path.pop()
    return path

def tourpath(V, E, path, m):    #构建哈密顿图第三步
    if (len(path) == m):
        path = tourpath1(V, E, path, m)
    while (len(path) != 0):
        path = tourpath0(V, E, path, m)
        if (len(path) == m):
            break
        path = tourpath1(V, E, path, m)
    return path

def Hamitonpath(V, E, v0):      #构建哈密顿图
    global Ea, paths
    V = sorted(V)
    Ea = adjacentlist(V, E)
    paths = set({})
    path = [v0]
    m = len(V)
    path = tourpath(V, Ea, path, m)
    paths = paths | {tuple(path)}
    while (len(path) == m):
        path = tourpath(V, Ea, path, m)
        if (len(path) == m):
            paths = paths | {tuple(path)}
            # print(path)
    return paths

def shortpath(V, E, di, Hx, path, zn):  #寻找短路径
    V = sorted(V)
    Pm = []
    for p in path:
        vn = p[-1]
        if vn == zn:
            Pm = Pm + [p]
            continue
        # if di[V.index(vn)] != 0:
        #     Pm = Pm + [p]
        #     continue
        for (w, u, v) in E:
            if u == vn:
                kv = V.index(v)
                if di[kv] > 0:
                    di[kv] = di[kv] - 1
                vw = p[0] + w
                if vw < Hx[kv]:
                    Hx[kv] = vw
                    e = [vw] + p[1:] + [v]
                    Pm = Pm + [e]
    return [di, Hx, Pm]

def shortestpath(V, E, v0, vn):     #寻找最短路径
    V = sorted(V)
    [d, di, do] = gt.degreesetw(V, E)
    Pm0 = []
    Pm = [[0, v0]]
    inf = 10000
    Hx = [inf for x in range(len(V))]
    Hx[0] = 0
    while Pm0 != Pm:
        Pm0 = Pm
        [di, Hx, Pm] = shortpath(V, E, di, Hx, Pm0, vn)
    Pm = sorted(Pm)
    return [Hx, Pm[0]]

def Huffmantree(W):             #构建霍夫曼树
    W0 = []
    for [a, w] in W:
        W0 = W0 + [[w, a]]
    tree = sorted(W0)
    while len(tree) != 1:
        w = tree[0][0] + tree[1][0]
        w = math.floor(w * 10000) / 10000
        tree = [[w, tree[0], tree[1]]] + tree[2:]
        tree = sorted(tree)
    return tree[0]

def huffmancoding(subtree, code):   #构建霍夫曼子树编码
    if len(subtree) == 2:
        return [[subtree[1], code]]
    else:
        node0 = subtree[1]
        node1 = subtree[2]
        code = huffmancoding(node0, code + '0') + huffmancoding(node1, code + '1')
        return code

def HuffmanCoding(tree):        #构建霍夫曼编码
    code0 = huffmancoding(tree[1], '0')
    code1 = huffmancoding(tree[2], '1')
    return code0 + code1

def weightcmp(x):
    return x[2]

def Primspanttree(V, E):        #普林算法
    E = sorted(E, key=weightcmp)
    [u, v, w] = E[0]
    Vt = {u, v}
    Et = {(u, v, w)}
    del E[0]
    n = len(V)
    while len(Et) < (n - 1):
        i = 0
        while (i < len(E)):
            [u, v, w] = E[i]
            if (u in Vt and v not in Vt) or (u not in Vt and v in Vt):
                Et = Et | {(u, v, w)}
                Vt = Vt | {u, v}
                del E[i]
                break
            i = i + 1
    return [Vt, Et]

def iscycled(V, E, u0, v0):     #是否成环
    tv = False
    Vc = {u0, v0}
    Ec = {(u0, v0)}
    n = 0
    while (n != len(Vc)):
        n = len(Vc)
        for (u, v, w) in E:
            if (u in Vc) and (v in Vc):
                tv = True
                return tv
            if ((u in Vc) and (v not in Vc)) or ((u not in Vc) and (v in Vc)):
                Ec = Ec | {(u, v)}
                Vc = Vc | {u, v}
                E = E - {(u, v, w)}
                break
    return tv

def Kruskalspantree(V, E):      #克鲁斯卡尔算法
    E = sorted(E, key=weightcmp)
    Vt = set({})
    Et = set({})
    n = len(V)
    k = 0
    i = 0
    while (len(Et) < n - 1):
        [u, v, w] = E[i]
        i = i + 1
        if (u in Vt) and (v in Vt):
            if iscycled(Vt, Et, u, v):
                continue
        Et = Et | {(u, v, w)}
        Vt = Vt | {u, v}
    return [Vt, Et]

def subEulercircuit(E, v0):     #构建欧拉子图
    circuit = tuple([v0])
    S = set({})
    while (circuit[0] != circuit[-1] or len(circuit) == 1):
        y = circuit[-1]
        for (u, v) in E:
            if (u == y):
                circuit = circuit + tuple([v])
                E = E - {(u, v)}
                S = S | {(u, v)}
                break
    return [circuit, S]

def set2V(E):
    V = set({})
    for (u, v) in E:
        V = V | {u, v}
    return V

def Eulercircuit(E, v0):        #构建欧拉图
    [circuit, S] = subEulercircuit(E, v0)
    E = E - S
    while (E != set({})):
        V1 = set(circuit)
        V2 = set2V(E)
        V1V2 = V1 & V2
        for v0 in V1V2:
            [subcircuit, S] = subEulercircuit(E, v0)
            if S == set({}):
                continue
            k = circuit.index(v0)
            circuit = circuit[0: k] + subcircuit + circuit[k + 1 : -1] + tuple([circuit[-1]])
            E = E - S
            break
    return circuit

def Knighttouregraph(n):        #骑士周游图
    P8 = [[-1, 2], [-2, -1], [-2, 1], [-1, 2],\
          [1, 2], [2, 1], [2, -1], [1, -2]]
    N = n * n
    V = list(range(N))
    E = set({})
    for k in range(N):
        j = k % n
        i = int(k / n)
        for [u, v] in P8:
            if 0 <= (i + u) and (i + u) < n\
                    and 0 <= (j + v) and (j + v) < n:
                E = E | {(k, (i + u) * n + (j + v))}
    return [V, E]

def stepu0v(di0, E):        #入度为0
    S = set({})
    for u0 in di0:
        for (w, u, v) in E:
            if u == u0:
                S = S | {(w, u, v)}
    return S

def stepuv0(do0, E):        #出度为0
    S = set({})
    for v0 in do0:
        for (w, u, v) in E:
            if v == v0:
                S = S | {(w, u, v)}
    return S

def TEpath(S, Hx, di):
    di0 = set({})
    for (w, u, v) in S:
        if Hx[v] < Hx[u] + w:
            Hx[v] = Hx[u] + w
        if di[v] > 0:
            di[v] = di[v] - 1
        if di[v] == 0:
            di0 = di0 | {v}
    return [Hx, di, di0]

def TLpath(S,Hy,do):
    do0=set({})
    for (w, u, v) in S:
        if Hy[u] > Hy[v] - w:
            Hy[u] = Hy[v] - w
        if do[u]>0:
            do[u] = do[u] - 1
        if do[u] == 0:
            do0 = do0 | {u}
    return [Hy,do,do0]